MOD = 1000000009

def ksm(a, b):
    res = 1
    while b:
        if b&1:
            res = res*a % MOD
        a = a*a % MOD
        b >>= 1
    return res % MOD

a, b = map(int, input().split())
print(ksm(a,b))
